#pragma once
#include <climits>
#include <vector>
#include <unordered_map>
#include <iostream>
using namespace std;

template <class V, class W, W MAX_W = INT_MAX, bool Direction = false>
class Graph
{

public:
    typedef Graph<V, W, MAX_W, Direction> Self;
    Graph() = default; // 生成默认构造函数
    Graph(const V *arr, size_t n)
    {
        _vertexs.reserve(n); // 容量至少开n个
        for (size_t i = 0; i < n; ++i)
        {
            _vertexs.push_back(arr[i]);
            _vIndexMap[arr[i]] = i;
        }
        _matrix.resize(n);
        for (size_t i = 0; i < _matrix.size(); ++i)
        {
            _matrix[i].resize(n, MAX_W);
        }
    }

    size_t GetVertexIndex(const V &vertex)
    {
        auto iter = _vIndexMap.find(vertex);
        if (iter == _vIndexMap.end())
        { // 不存在该顶点
            // assert(false);
            return -1;
        }
        return iter->second;
    }

    // 建立两个顶点的连接路径
    void AddEdge(const V &src, const V &dst, const W &w)
    {
        int srci = GetVertexIndex(src);
        int dsti = GetVertexIndex(dst);
        _matrix[srci][dsti] = w;
        if (Direction == false)
        {
            _matrix[dsti][srci] = w;
        }
    }

    void Print()
    {
        // 打印顶点和下标映射关系
        for (size_t i = 0; i < _vertexs.size(); ++i)
        {
            cout << _vertexs[i] << "-" << i << " ";
        }
        cout << endl
             << endl;
        cout << " ";
        for (size_t i = 0; i < _vertexs.size(); ++i)
        {
            cout << i << " ";
        }
        cout << endl;
        // 打印矩阵
        for (size_t i = 0; i < _matrix.size(); ++i)
        {
            cout << i << " ";
            for (size_t j = 0; j < _matrix[i].size(); ++j)
            {
                if (_matrix[i][j] != MAX_W)
                    cout << _matrix[i][j] << " ";
                else
                    cout << "#" << " ";
            }
            cout << endl;
        }
        cout << endl
             << endl;
        // 打印所有的边
        for (size_t i = 0; i < _matrix.size(); ++i)
        {
            for (size_t j = 0; j < _matrix[i].size(); ++j)
            {
                if (_matrix[i][j] != MAX_W)
                {
                    cout << _vertexs[i] << "-" << _vertexs[j] << ":" << _matrix[i][j] << endl;
                }
            }
        }
    }

private:
    unordered_map<V, int> _vIndexMap;
    vector<V> _vertexs;        // 顶点的集合
    vector<vector<W>> _matrix; // 存储边集合的矩阵
};

void TestGraph()
{
    Graph<char, int, INT_MAX, true> g("0123", 4);
    g.AddEdge('0', '1', 1);
    g.AddEdge('0', '3', 4);
    g.AddEdge('1', '3', 2);
    g.AddEdge('1', '2', 9);
    g.AddEdge('2', '3', 8);
    g.AddEdge('2', '1', 5);
    g.AddEdge('2', '0', 3);
    g.AddEdge('3', '2', 6);
    g.Print();
}

namespace LinkTable
{
    template <class W>
    class LinkEdge
    {
    public:
        LinkEdge(const int &desti, const W &w) : _desti(desti), _next(nullptr), _w(w)
        {
        }
        int _desti;
        W _w;
        LinkEdge<W> *_next;
    };

    template <class V, class W, W MAX_I = INT_MAX, bool Direction = false> // false 表示是无向图
    class Graph
    {
        typedef  LinkEdge<W>  _LinkEdge;
    public:
        Graph(const V *vertexs, size_t n)
        {
            for (size_t i = 0; i < n; ++i)
            {
                _vertexs.push_back(vertexs[i]);
                _vIndexMap[vertexs[i]] = i;
            }
            _LinkTable.resize(n, nullptr);
        }

        size_t GetVertexIndex(const V &vertex)
        {
            auto iter = _vIndexMap.find(vertex);
            if (iter != _vIndexMap.end())
            {
                return iter->second;
            }
            else
            {
                // 出错
                return -1;
            }
        }

        void AddEdge(const V &src, const V &dest, const W &w)
        {
            size_t srci = GetVertexIndex(src);
            size_t desti = GetVertexIndex(dest);
            _LinkEdge *newEdge = new _LinkEdge(desti, w);
            // 头插法
            newEdge->_next = _LinkTable[srci];
            _LinkTable[srci] = newEdge;
            if (Direction == false)
            {
                _LinkEdge *newEdge = new _LinkEdge(srci, w);
                newEdge->_next = _LinkTable[desti];
                _LinkTable[desti] = newEdge;
            }
        }

        void Print()
        {
            for(size_t i = 0 ; i < _vertexs.size() ; ++ i)
            {
                std::cout<< "["<< i <<"]"<<"->"<<_vertexs[i]<<endl;
            }
            cout<<endl;
            for(size_t i = 0 ; i < _LinkTable.size() ; ++ i)
            {
               auto cur =  _LinkTable[i];
               cout<< _vertexs[i] << "["<<i<<"]"<<"->";
                while(cur)
                {
                    cout<<"[" <<_vertexs[cur->_desti]<<":"<< cur->_desti<<":"<<cur->_w<<"]->";
                    cur = cur->_next;
                }
                cout<< "nullptr"<<endl;
            }
        }

    private:
        unordered_map<V, int> _vIndexMap;
        vector<V> _vertexs;
        vector<_LinkEdge *> _LinkTable; // 边的集合
    };

    void TestGraph()
    {
        string a[] = {"张三", "李四", "王五", "赵六"};
        Graph<string, int , true > g1(a, 4);
        g1.AddEdge("张三", "李四", 100);
        g1.AddEdge("张三", "王五", 200);
        g1.AddEdge("王五", "赵六", 30);
        g1.Print();
    }

};